perm filename WINGED[0,BGB]3 blob
sn#102640 filedate 1974-05-19 generic text, type C, neo UTF8
COMMENT ⊗ VALID 00009 PAGES
C REC PAGE DESCRIPTION
C00001 00001
C00002 00002 2.0 The Winged Edge Polyhedron Representation.
C00005 00003 2.1 Winged Edge Link Fields.
C00010 00004
C00013 00005 2.2 Perimeter Accessing.
C00017 00006 2.3 Edge and Face Splitting.
C00019 00007
C00021 00008 2.4 Lowest Level Polyhedron Synthesis.
C00024 00009 2.5 Coordinate Free Polyhedron Representation.
C00027 ENDMK
C⊗;
2.0 The Winged Edge Polyhedron Representation.
2.1 Winged Edge Link Fields.
2.2 Perimeter Accessing.
2.3 Edge and Face Splitting.
2.4 Basic Polyhedron Synthesis.
2.5 Coordinate Free Polyhedron Representation.
2.0 Introduction.
In this chapter, a particular computer representation for
polyhedra is presented and some of its virtues are explained. The
representation has been implemented as a data structure composed of
small blocks of words containing pointers and data in the fashion
usual to graphics and simulation; an introduction to this technology
can be found in Knuth (Art of Programming, chapter 2, volume I).
Quickly reviewing Knuth's notation and terminolgy: a node is a group
of consecutive words of memory, a field is a named portion of a node,
a link is the absolute machine address of a node and the notation for
referring to a field of a node consists simply of the field name
followed by a link expression enclosed in parentheses. For example
the two faces of an edge node, whoes link is stored in the variable
EDGE, are found in the fields named NFACE and PFACE, and are referred
to as NFACE(EDGE) and PFACE(EDGE). Although the latest language of
implementation is PDP-10 machine code, earlier versions were coded
in LISP and Stanford ALGOL (SAIL with LEAP). However, examples of
programs will be given in a programming language which is like an
ALGOL with Knuth node/link syntax added.
2.1 Winged Edge Link Fields.
A polyhedron in made up of four kinds of nodes: bodies,
faces, edges and vertices. The body node is the head of three rings:
a ring of faces, a ring of edges and a ring of vertices. Each face
and each vertex points at one of the edges on its perimeter. Each
edge points at its two faces and its two vertices. Completing the
structure, each edge node contains a link to each of its four
immediate neighboring edges clockwise and counter clockwise around
face perimeters (as seen from the exterior side of the surface of the
polyhedron). These last four links are the wings of the edge, which
provide the basis for efficient face and vertex perimeter accessing.
Finally, the links of the edge nodes can be consistently oriented
with respect to the surface of the polyhedron so that the surface
always has two sides: the inside and the outside.
Observe that there are twenty-two link fields in the basic
representation: bodies contain six links, faces three links, vertices
three links and edges ten links. Thus the least number of different
link field names that need to be coined is ten; if we allow a link
name such as PED to serve different roles depending on whether it
applies to a body, face, edge or vertex. The data structures and the
link fields comprising the structures are listed in table (**) below.
The ten links names include: NFACE and PFACE for two fields that
contain face links in edges and the face ring, NED and PED for two
fields that contain edge links, NVT and PVT for two fields that
contain vertex links, and NCW, PCW, NCCW and PCCW for the four fields
that contain edge links and are called the wings.
---------------------------------------------------------------------
TABLE Data Structure Link Names
1. Face Ring of a Body. NFACE PACE
2. Edge Ring of a Body. NED PED
3. Vertex Ring of a Body. NVT PVT
4. First Edge of a Vertex. PED
5. First Edge of a Face. PED
6. The two faces of an edge: NFACE PFACE
7. The two vertices of an edge: NVT PVT
8. The four wing edges of an edge: NCW PCW
NCCW PCCW
---------------------------------------------------------------------
As mentioned, advantage can be realized by constraining the
links of edge nodes to indicate a surface orientataion (interior and
exterior) and a linear orientation (directed vector). Since there are
four possible ways to put a pair of faces and a pair of vertices into
a pair of face fields and a pair of vertex fields; both surface and
linear orientation can be encoded. Viewing an edge of an existing
polyhedron (from the exterior side of its surface), the links are
arranged as illustrated in the figure (**). Appropriate subroutines
for creating, maintaining and exploiting edge orientation are
explained in later sections. Notice that although the vertices in the
figure are shown with only three edges, vertices may in fact have any
number of edges. The other potential edges would not be directly
connected to the middle edge of the figure and so were not shown.
FIGURE - THE WINGED EDGE.
(As viewed from the exterior of a solid).
\ /
NCCW(E) \ / PCW(E)
\ /
\ /
\ /
⊗ PVT(E)
|
|
NFACE(E) | E PFACE(E)
|
|
NVT(E) ⊗
/ \
/ \
/ \
NCW(E) / \ PCCW(E)
/ \
Next, it is necessary to mention some of the data fields. The
3-D coordinates of each vertex are kept in fields named XWC, YWC and
ZWC; the "WC" standing for "world coordinates". The 3-D perspective
projected coordinates of each vertex with respect to one camera at a
time are kept in fields named XPP, YPP, ZPP of vertex nodes. Faces on
the other hand carry exterior pointing normal vectors and three words
of photometric data.
2.2 Perimeter Accessing.
Given one edge of a face or vertex perimeter, the next edge
clockwise or counter clockwise from the given edge about the
particular face or vertex can be retrieved from the data structure
with the assistance of two subroutines called ECW and ECCW. The idea
of the edge clocking routines is to match the given face or vertex
with one of the faces and vertices of the given edge and to then
return the appropriate wing. One possible coding of ECCW and ECW might
be as follows:
COMMENT FETCH EDGE COUNTER CLOCKWISE FROM E ABOUT FV;
INTEGER PROCEDURE ECCW (INTEGER E,FV);
BEGIN "ECCW"
IF PFACE(E)=FV THEN RETURN(PCCW(E));
IF NFACE(E)=FV THEN RETURN(NCCW(E));
IF PVT(E)=FV THEN RETURN(PCW(E));
IF NVT(E)=FV THEN RETURN(NCW(E));
FATAL;
END "ECCW";
COMMENT FETCH EDGE CLOCKWISE FROM E ABOUT FV;
INTEGER PROCEDURE ECW (INTEGER E,FV);
BEGIN "ECW"
IF PFACE(E)=FV THEN RETURN(PCW(E));
IF NFACE(E)=FV THEN RETURN(NCW(E));
IF PVT(E)=FV THEN RETURN(NCCW(E));
IF NVT(E)=FV THEN RETURN(PCCW(E));
FATAL;
END "ECW";
The first edge of a face or vertex is (of course) directly
available from the PED field of the face or vertex. For example, the
code fragment below can be used to visit all the edges of a face.
COMMENT APPLY A FUNTION TO ALL THE EDGES OF A FACE;
BEGIN
INTEGER F,E,E0;
E←E0←PED(F);
DO FUNCTION(E) UNTIL E0=(E←ECCW(E,F));
END;
Almost the same code fragment can be used to travel the perimeter
of a vertex.
COMMENT APPLY A FUNTION TO ALL THE EDGES OF A VERTEX;
BEGIN
INTEGER V,E,E0;
E←E0←PED(V);
DO FUNCTION(E) UNTIL E0=(E←ECCW(E,V));
END;
Following the same idea as the edge clocking routines, a new
face or vertex can be retrieved relative to a given edge and a given
face or vertex. These routines include: FCW and FCCW which return the
face clockwise or counter clockwise from a given edge with respect to
a given vertex; VCW and VCCW which return the vetex clockwise or
counter clockwise from a given edge with respect to a given face; and
OTHER which return the face or vertex of the given edge opposite the
given face or vertex. Together the seven routines: ECW, ECCW, VCW,
VCCW, FCW, FCCW and OTHER exhaust the possible oriented retrievals
from an edge node; they also alleviate the need to any explicit
reference a wing field when traveling the surface of a polyhedron.
2.3 Edge and Face Splitting.
Another simple virture of the winged edge representation is
that edges and faces can be split using subroutines involving only
local alterations to the data structure. Likewise, the splits can
be easily removed, in fact the main reason for doubly linked rings is
for the sake of rapid deletion of nodes. The edge split routine,
ESPLIT, makes a new edge and a new vertex and places them into the
surface topology as shown in figure (**). The kill edge-vertex
routine, KLEV, undoes an ESPLIT. The face split routine, MKFE,
creates a new edge and a new face and places them into the surface
topology as shown in figure (**); the kill face-edge routine, KLFE,
undoes a MKFE.
---------------------------------------------------------------------
FIGURES FOR ESPLIT & MKFE.
VNEW ← ESPLIT(E); E ← KLEV(VNEW);
ENEW ← MKFE(V1,F,V2); F ← KLFE(ENEW);
INTEGER PROCEDURE ESPLIT (INTEGER E);
BEGIN "ESPLIT"
INTEGER VNEW,ENEW,
COMMENT CREATE A NEW EDGE AND VERTEX ON THE BODY;
VNEW ← MKV(E);
ENEW ← MKE(E);
COMMENT CONNECT VERTICES AND FACES TO EDGES;
PVT(ENEW) ← PVT(E);
NVT(ENEW) ← VNEW;
PVT(E) ← VNEW;
PFACE(ENEW) ← PFACE(E);
NFACE(ENEW) ← NFACE(E);
COMMENT CONNECT EDGES TO VERTICES;
IF PED(V)=E THEN PED(V)←ENEW;
PED(VNEW)←ENEW;
COMMENT LINK THE WINGS TOGETHER;
NCW(ENEW) ← E; PCCW(ENEW) ← E;
PCW(E) ← ENEW; PCCW(E) ← ENEW;
WING(NCCW(E),ENEW);
WING(PCW(E),ENEW);
RETURN(VNEW);
END "ESPLIT";
2.4 Lowest Level Polyhedron Synthesis.
The general problem of synthesizing polyhedra encompasses
descriptive computer vision in that an advanced modeling program
should be able to make a description by looking at an object through
a television camera. However, for the moment consider the problem
internal to the modeling system where the geometry and topology of a
given polyhedron are available in some given format and a winged edge
model is desired.
In the typical situation, there are five steps: first, get
the proper kinds of nodes into the body rings using the MKF, MKE, MKV
primitives. second, place the vertices by setting their XWC, YWC, ZWC
fields; third, connect each vertex and face pointed to one of its
edges by setting their PED fields. fourth, connect each edge to its
two faces and its two vertices by setting their NFACE, PFACE, NVT,
PVT fields. Finally, create the wing perimeter pointers by applying
the WING primitive to pairs of edges to be mated.
The data structure given in section 2.1 is
redundant, consider for a moment which of the nodes and links can be
computed from the others.
For example the wing pointers can be restored from the face-vertex pointers.
all the edges of a polyhedron could be compare
N*(N-1)/2 comparisons
---------------------------------------------------------------------
WINGED EDGE PRIMITIVES:
1-5 MKB,MKF,MKE,MKV,MKFRAME. Make B.F.E.V. nodes.
{KLB},{KLF},{KLE},{KLV}. Kill B.F.E.V. nodes.
6,7,8 WING,INVERT,EVERT Make and change wing pointers.
9. LINKED Find if two entities are linked.
10,11 ECW,ECCW,{EFETCH} Edge fetching around F.V. perimeters.
12-16 OTHER,VCW,VCCW,FCW,FCCW Face/Vertex fetching from an edge.
17-19 BDET,BATT,BGET Body parts linking and body get.
2.5 Coordinate Free Polyhedron Representation.
As in general relativity, geometric entities can be
represented in a coordinate free form. In particular, the vertex
coordinates of a polyhedra can be recovered from edge lengths and
dihedral angles (the angle formed by the two faces at each edge).
Having the geometry carried by only two numbers per edge rather than
by three numbers per vertex does not yield a more concise
representation because edges always outnumber vertices and in the
case of a triangulated polyhderon edges outnumber vertices by three
to one.
One application of a coordinate free representation arises
when it is necessary to measure a complicated shape with simple tools
such as a caliper and straight edge. For example, one way to go about
recording the topology and geometry of an arbitrary object is to draw
a triangulated polyhedron on its surface with serial numbered
vertices and record for each edge its length, its two vertices and
its "signed dihedral length". The dihedral length is the distance
between the vertices opposite the edge in each of the edge's two
triangles, the length can be given a sign convention to indicate
whether the edge is concave or convex. The required dihedral angles
can then be computed from the signed dihedral lengths.